const { Dictionary } = require('./dictionary');

class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected; // 可以接收一个参数来表示图是否有向
    this.vertices = []; // 用一个数组来存储图中所有顶点的名字
    this.adjList = new Dictionary(); // 一个字典来存储邻接表。字典将会使用顶点的名字作为键，邻接顶点列表作为值
  }

  /**
   * 向图中添加一个新的顶点
   * @param {*} v 顶点
   */
  addVertex(v) {
    // 顶点不存在于图中时
    if (!this.vertices.includes(v)) {
      this.vertices.push(v); // 将该顶点添加到顶点列表中
      this.adjList.set(v, []); // 在邻接表中，设置顶点v作为键对应的字典值为一个空数组
    }
  }

  /**
   * 添加顶点之间的边
   * @param {*} v 接受顶点作为参数
   * @param {*} w
   */
  addEdge(v, w) {
    // 如果顶点v不存在于图中
    if (!this.adjList.get(v)) {
      this.addVertex(v); // 加入顶点列表
    }
    // 如果顶点w不存在于图中
    if (!this.adjList.get(w)) {
      this.addVertex(w); // 加入顶点列表
    }
    this.adjList.get(v).push(w); // 添加一条自顶点v到顶点w的边，如果想实现的事一个有向图，则这一行就够了
    if (!this.isDirected) {
      this.adjList.get(w).push(v);
    }
  }

  /**
   * 返回顶点列表
   * @returns
   */
  getVertices() {
    return this.vertices;
  }

  /**
   * 返回邻接表
   * @returns
   */
  getAdjList() {
    return this.adjList;
  }

  toString() {
    let s = '';
    // 迭代vertices数组列表，将顶点的名字加入字符串中
    for (let i = 0; i < this.vertices.length; i++) {
      s += `${this.vertices[i]} -> `;
      const neighbors = this.adjList.get(this.vertices[i]);
      // 迭代邻接表，将相邻顶点加入字符串
      for (let j = 0; j < neighbors.length; j++) {
        s += `${neighbors[j]}`;
      }
      s += '\n'; // 添加换行符
    }
    return s;
  }
}

exports.Graph = Graph;
